//
// Created by francklinson on 2021/8/2 AT 0:07.
//

//有 n 个网络节点，标记为1到 n。
//
//给你一个列表times，表示信号经过 有向 边的传递时间。times[i] = (ui, vi, wi)，
//其中ui是源节点，vi是目标节点， wi是一个信号从源节点传递到目标节点的时间。
//现在，从某个节点K发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回-1 。


#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <functional>
#include <climits>

using namespace std;

class Solution {
public:
    int networkDelayTime(vector<vector<int>> &times, int n, int k) {
        // 相邻节点  存在数组中
        unordered_map<int, vector<pair<int, int>>> edges;
        for (auto &x:times) {
            edges[x[0]].emplace_back(x[1], x[2]);
        }
        // 信号最早到达的时间
        vector<int> arrivedTime(n + 1, 100);
        // 是否遇见
        vector<bool> seen(n + 1, false);
        // bfs队列
        queue<pair<int, int>> q;
        q.emplace(k, 0);
        arrivedTime[k] = 0;
        seen[k] = true;
        while (!q.empty()) {
            auto[node, time] = q.front();
            q.pop();
            for (auto &[nextNode, delta]:edges[node]) {
                if (!seen[nextNode]) {
                    q.emplace(nextNode, time + delta);
                    seen[nextNode] = true;
                }
                arrivedTime[nextNode] = min(time + delta, arrivedTime[nextNode]);
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            // 存在没传递到的点
            if (seen[i] == false) return -1;
            ans = max(ans, arrivedTime[i]);
        }
        return ans;
        // 简单bfs  无法获得最优路径
    }
};

class Solution2 {
public:
    using pii = pair<int, int>;

    int networkDelayTime(vector<vector<int>> &times, int n, int k) {
        vector<vector<pii> > eg(n + 1);
        // 记录访问过程
        vector<int> vis(n + 1);
        int ans = 0;
        for (auto &x: times) {
            eg[x[0]].emplace_back(x[1], x[2]);
        }
        priority_queue<pii, vector<pii>, greater<> > q;// 小堆顶  寻找「未确定节点」中与起点距离最近的点
        q.emplace(0, k);
        while (!q.empty()) {
            auto[time, now] = q.top();
            q.pop();
            if (vis[now])continue;
            ans = max(ans, time);
            vis[now] = true;
            // 加入相邻节点
            for (auto[next, nextTime]: eg[now]) {
                if (vis[next] == false)
                    q.emplace(nextTime + time, next);
            }
        }
        return count(begin(vis) + 1, end(vis), true) == n ? ans : -1; // 是不是都遍历过了
    }
};
class Solution3 { // 题解 单源最短路径  Dijkstra 算法
public:
    int networkDelayTime(vector<vector<int>> &times, int n, int k) {
        const int inf = INT_MAX / 2;
        vector<vector<int>> g(n, vector<int>(n, inf));
        for (auto &t : times) {
            int x = t[0] - 1, y = t[1] - 1;
            g[x][y] = t[2];
        }

        vector<int> dist(n, inf); // 各点到达时间记录
        dist[k - 1] = 0;     // 初始点
        vector<int> used(n); // 过程记录
        for (int i = 0; i < n; ++i) {
            int x = -1;
            // 从未访问节点中，找到距离起点最近的  即dist最小的
            for (int y = 0; y < n; ++y) {
                if (!used[y] && (x == -1 || dist[y] < dist[x])) {
                    x = y;
                }
            }
            used[x] = true;
            // 用找到的点x去更新距离   如果有相连，就会把inf变小
            for (int y = 0; y < n; ++y) {
                dist[y] = min(dist[y], dist[x] + g[x][y]);
            }
        }

        int ans = *max_element(dist.begin(), dist.end());
        return ans == inf ? -1 : ans;
    }
};


int main() {
    vector<vector<int>> times{{1, 2, 1},
                              {2, 3, 2},
                              {1, 3, 4}};
    Solution3 solution;
    cout << solution.networkDelayTime(times, 3, 1) << endl;

    vector<vector<int>> times2{{2, 1, 1},
                               {2, 3, 1},
                               {3, 4, 1}};
    cout << solution.networkDelayTime(times2, 4, 2) << endl;
    return 0;
}

